package lib;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class LongBitSet {
	
	//because the maximum array length is limited...
	private long MAX_SIZE = Long.MAX_VALUE >> 1; //because we can't use the negative Longs 
	
	private class BitSetPair {
		BitSet values;
		BitSet status;
		
		BitSetPair() {
			values = new BitSet();
			status = new BitSet();
		}
		
		BitSetPair(BitSet values, BitSet status) {
			this.values = values;
			this.status = status;
		}
		
		public void set(int index, boolean value) {
			if (value) values.set(index);
			status.set(index);
		}
		
		public boolean isSet(int index) {
			return status.get(index);
		}
		
		public boolean get(int index) {
			return values.get(index);
		}
		
	}
	
	List<BitSetPair> values = new ArrayList<BitSetPair>();
	
	public LongBitSet() {
		this(new BitSet(), new BitSet());
	}
	
	/**
	 * Use this constructor if you want to retain access to the bitsets of the first bin,
	 * so you don't have to do bin lookups for numbers below Integer.MAX_VALUE 
	 * @param firstBlockValues
	 * @param firstBlockStatus
	 */
	public LongBitSet(BitSet firstBlockValues, BitSet firstBlockStatus) {
		values.add(new BitSetPair(firstBlockValues,firstBlockStatus));
	}
	
	
	public boolean isSet(long index) {
		int bin = getBin(index);
		return (values.size() > bin ? values.get(bin).isSet(getPos(index)) : false);
	}
	
	public boolean get(long index) {
		return getBlock(index).get(getPos(index));
	}
	
	public void set(long index) {
		set(index, true);
	}
	
	public void set(long index, boolean value) {
		if (index > MAX_SIZE) throw new ArrayIndexOutOfBoundsException(index + " is greater than " + MAX_SIZE);
		BitSetPair block = getBlock(index);
		block.set(getPos(index), value);
	}
	
	private BitSetPair getBlock(long index) {
		int bin = getBin(index);
		ensureCapacityUpToBin(bin);
		return values.get(bin);
	}
	
	private void ensureCapacityUpToBin(int bin) {
		if (values.size() <= bin) {
			for (int b = values.size(); b <= bin; b++)
			values.add(new BitSetPair());
		}
	}
	
	private int getBin(long index) {
		return (int)(index >> 31);
	}
	
	private int getPos(long index) {
		return (int)(index % (Integer.MAX_VALUE + 1L));
	}

	public int nextClearBit(long i) {
		return getBlock(i).values.nextClearBit(getPos(i));
	}

}
